/******************************************************************************************************
*******************************************************************************************************
**************************************                        *****************************************
**************************************       COMPRESSING      *****************************************
**************************************                        *****************************************
*******************************************************************************************************
******************************************************************************************************/
#include <stdio.h>
#include <iostream.h>
#include <process.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#define BITS 12                   /* Setting the number of bits to 12, 13 or 14*/
#define HASHING_SHIFT BITS-8      
#define MAX_VALUE (1 << BITS) - 1 
#define MAX_CODE MAX_VALUE - 1    
				  
#if BITS == 14
  #define TABLE_SIZE 18041       
#endif                           
#if BITS == 13                   
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;                   /* This is the code value array        */
unsigned int *prefix_code;         /* This array holds the prefix codes   */
unsigned char *append_character;   /* This array holds the appended chars */
unsigned char decode_stack[4000];  /* This array holds the decoded string */

   /************************************************************************
    **
    **         This program gets a file name from the command line.  
    **     It compresses the file, placing its output in a file named test.lzw. 
    **
    *************************************************************************/

class compression
{
	public :

      /**********************************************************************
      ** 
      **                 This is the compression routine.  
      **
      ***********************************************************************/

	compress(FILE *input,FILE *output)
	{
		unsigned int next_code;
		unsigned int character;
		unsigned int string_code;
		unsigned int index;
		int i;

		next_code=256;              /* Next code is the next available string code*/
		for (i=0;i<TABLE_SIZE;i++)  /* Clear out the string table before starting */
			code_value[i]=-1;

		i=0;
		cout <<"Compressing...\n";
		string_code=getc(input);        /* Get the first code   */

       /******************************************************************************
       **      
       **    This loop runs util all of the input has been exhausted .
       **    Note that it stops adding codes to the
       **    table after all of the possible codes have been defined.
       **
       *******************************************************************************/
		
                while ((character=getc(input)) != (unsigned)EOF)
		{
			if (++i==1000)           /* Print a * every 1000 */
			{                        /* input characters.  */
				i=0;             
				cout <<"*";
			}
			index=find_match(string_code,character);/* See if the string is in */
			if (code_value[index] != -1)            /* the table.  If it is,   */
				string_code=code_value[index];  /* get the code value.     */
			else                                    /*If the string is not in the*/
			{                                       /* table, try to add it.   */
				if (next_code <= MAX_CODE)
				{
					code_value[index]=next_code++;
					prefix_code[index]=string_code;
					append_character[index]=character;
				}
				output_code(output,string_code);  /* When a string is found  */
				string_code=character;            /* that is not in the table*/
			}                                         /*  output the last string*/
		}                                                 /* after adding the new one*/

            

                       /**************************************************
                        **            End of the main loop.
                        ***************************************************/
		

                output_code(output,string_code); /* Output the last code               */
		output_code(output,MAX_VALUE);   /* Output the end of buffer code      */
		output_code(output,0);           /* This code flushes the output buffer*/
		cout <<"\n";
	}


           /*****************************************************************************
           ** This is the hashing routine.  It tries to find a match for the prefix+char
           ** string in the string table.  If it finds it, the index is returned.  If
           ** the string is not found, the first available index in the string table is
           ** returned instead.
           *******************************************************************************/

	find_match(int hash_prefix,unsigned int hash_character)
	{
		int index;
		int offset;

		index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
		if (index == 0)
			offset = 1;
		else
			offset = TABLE_SIZE - index;
		while (1)
		{
			if (code_value[index] == -1)
				return(index);
			if (prefix_code[index] == hash_prefix &&
				append_character[index] == hash_character)
				return(index);
			index -= offset;
			if (index < 0)
				index += TABLE_SIZE;
		}
	}



       /*********************************************************************
       ** The following two routines are used to output variable lengthcodes.
       *************************************************************************/

	output_code(FILE *output,unsigned int code)
	{
		static int output_bit_count=0;
		static unsigned long output_bit_buffer=0L;

		output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
		output_bit_count += BITS;
		while (output_bit_count >= 8)
		{
			putc(output_bit_buffer >> 24,output);
			output_bit_buffer <<= 8;
			output_bit_count -= 8;
		}
	}
}
//////////////////////////////////////////////
main()
{
	compression com;
	FILE *input_file;
	FILE *output_file;
	FILE *lzw_file;
	char input_file_name[81];

           /*******************************************************************
            **  The three buffers are needed for the compression phase.
            *******************************************************************/


	code_value=(int*)malloc(TABLE_SIZE*sizeof(unsigned int));
	prefix_code=(unsigned int*)malloc(TABLE_SIZE*sizeof(unsigned int));
	append_character=(char *)malloc(TABLE_SIZE*sizeof(unsigned char));
	if (code_value==NULL || prefix_code==NULL || append_character==NULL)
	{
		cout <<"Fatal error allocating table space!\n";
		exit(1);
	}

        /****************************************************************************
         **  Get the file name, open it up, and open up the lzw output file.
         ****************************************************************************/
	
        
	cout <<"Input file name? ";
	scanf("%s",input_file_name);
	
	input_file=fopen(input_file_name,"rb");
	lzw_file=fopen("test.lzw","wb");
	if (input_file==NULL || lzw_file==NULL)
	{
		cout <<"Fatal error opening files.\n";
		exit(1);
	}

             /***********************************************************
             **                     Compress the file.
             ************************************************************/
	
        com.compress(input_file,lzw_file);
	fclose(input_file);
	fclose(lzw_file);
	free(code_value);

}
